package Other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class leet_54 {
    public static void main(String[] args) {
        Solution_54 p =new Solution_54();
        int[][] matrix = new int[2][4];
        p.simulation(matrix);
    }

}

class Solution_54 {

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = simulation(matrix);
        return result;
    }

    /**
     * 模拟法进行迭代
     * @param matrix  矩阵
     * @return
     */
    public List<Integer> simulation(int[][] matrix){
        // 返回的List
        List<Integer> result = new ArrayList<>();
        // 首先构建一个 用来存放是否行进到这个地方过
        boolean[][] newMatrix = new boolean[matrix.length][matrix[0].length];
        // 遍历的次数
        int allStep = matrix.length * matrix[0].length;
        // 方向
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // 起点
        int row = 0;
        int columns = 0;
        // 调整方向的指针
        int directionIndex = 0;
        for(int i=0; i<allStep; i++){
            // 元素加入数组
            result.add(matrix[row][columns]);
            // 该位置的遍历判断
            newMatrix[row][columns] = true;
            // 转向指针
            int nextRow = row + directions[directionIndex][0];
            int nextColumns = columns + directions[directionIndex][1];
            if(nextRow<0 || nextRow>matrix.length-1 || nextColumns<0 ||
                    nextColumns>matrix[0].length-1 || newMatrix[nextRow][nextColumns]==true)
            {
                // 当到达边界时
                directionIndex = (directionIndex+1)%4;
            }
            // 判断是否改变方向的指针后的下一步
            row = row + directions[directionIndex][0];
            columns = columns + directions[directionIndex][1];
        }
        return result;
    }


    /**
     * 利用圈层法  一圈一圈的层级
     * 将数组看层圈层，走外面一圈时 方向是 右->下->左->上
     * 里面一个圈层是 右->下->左->上
     * 顺序没有不同 只是每次边界需要缩小
     *
     * @param matrix  数组
     * @return
     */
    public  List<Integer> layers(int[][] matrix){
        List<Integer> result = new ArrayList<Integer>();
        // 四个方向
        int top = 0;
        int left = 0;
        int bottom = matrix.length-1;
        int right = matrix[0].length-1;


        while(left<=right && top<=bottom) {
            // 会出现 只剩下一个格子时或者只有一列时会有重复的问题
            // 单列
            if(left == right){
                for (int i = top; i <= bottom; i++) {
                    result.add(matrix[i][right]);
                }
                left = left + 1;
                right = right-1;
                continue;
            }

            // 单层
            if(top == bottom){
                // 左到右
                for (int i = left; i <= right; i++) {
                    result.add(matrix[top][i]);
                }
                top = top + 1;
                bottom = bottom - 1;
                continue;
            }


            // 左到右
            for (int i = left; i < right; i++) {
                result.add(matrix[top][i]);
            }
            // 上到下
            for (int i = top; i < bottom; i++) {
                result.add(matrix[i][right]);
            }
            // 右往左
            for (int i = right; i > left; i--) {
                result.add(matrix[bottom][i]);
            }
            // 下到上
            for (int i = bottom; i > top; i--) {
                result.add(matrix[i][left]);
            }

            // 第一层走完重新设计四个方向的值
            top = top + 1;
            left = left + 1;
            bottom = bottom - 1;
            right = right - 1;
        }

        return result;
    }


}

